use std::{
    cell::{RefCell, RefMut},
    collections::VecDeque,
    rc::Rc,
};

use ln_alg::{Tree, TreeNode};
fn main() {
    let _root = Rc::new(RefCell::new(init_tree()));

    println!("先序遍历：",);
    TreeNode::for_preorder(&_root);
    println!("中序遍历：",);
    TreeNode::for_inorder(&_root);
    println!("后序遍历：",);
    TreeNode::for_postorder(&_root);
    println!("层序遍历：",);
    TreeNode::for_layerorder(&_root);
    println!("线索二叉树的前序遍历",);
    TreeNode::for_morris_prev(&_root);
    println!("线索二叉树的中序遍历",);
    TreeNode::for_morris_mid(&_root);
    // println!("线索二叉树的后序遍历",);
    // TreeNode::for_morris_post(&_root);
}

trait TreeAlg {
    fn for_preorder(root: &Rc<RefCell<TreeNode>>);
    fn for_inorder(root: &Rc<RefCell<TreeNode>>);
    fn for_postorder(root: &Rc<RefCell<TreeNode>>);
    fn for_layerorder(root: &Rc<RefCell<TreeNode>>);
    fn for_morris_prev(root: &Rc<RefCell<TreeNode>>);
    fn for_morris_mid(root: &Rc<RefCell<TreeNode>>);
    fn for_morris_post(root: &Rc<RefCell<TreeNode>>);
}

impl TreeAlg for TreeNode {
    fn for_morris_post(root: &Rc<RefCell<TreeNode>>) {
        println!("不会写，TODO");
    }
    fn for_morris_mid(root: &Rc<RefCell<TreeNode>>) {
        let mut cur_node: Option<Rc<RefCell<TreeNode>>> = Some(Rc::clone(root));
        // 可以找到cur节点对应的左子树中最右边的节点
        while cur_node.is_some() {
            let cur = Rc::clone(cur_node.as_ref().unwrap());
            if let Some(most_right) = cur.borrow().get_child(1) {
                // 这里的“most_right”即当前节点的左子树中位于最右边的节点，即“前驱节点”
                let mut most_right = Rc::clone(most_right);
                while let Some(right_r_c) = Rc::clone(&most_right).borrow().get_child(0) {
                    // 开始寻找最右边的节点
                    // 直到找到最右边的节点(right_r_c为零)或者前驱节点正是当前节点的节点(right_r_c==cur)为止
                    if Rc::clone(right_r_c) == cur {
                        break;
                    } else {
                        most_right = Rc::clone(right_r_c);
                    }
                }
                // 到这里之后，便相当于找到了前驱节点。
                let most_right = most_right;
                if most_right.borrow().get_child(0).is_none() {
                    // 此时most_right.right == None，故建立线索指针
                    most_right.borrow_mut().l_child = Some(Rc::clone(&cur));
                    cur_node = Some(Rc::clone(cur.borrow().get_child(1).as_ref().unwrap()));
                    continue;
                } else {
                    // 此时most_right.right == cur，故删除线索指针
                    most_right.borrow_mut().r_child = None;
                }
            } else {
            }

            println!("{}", cur.borrow()); // 此时表示当前节点已经没有左孩子或者其前驱节点已经被访问过了
            cur_node = match cur.borrow().get_child(0) {
                // 此时的“右孩子”除了只非叶子节点的右孩子之外，也指叶子节点中的“后继节点”
                Some(r_c) => Some(Rc::clone(r_c)),
                None => None,
            };
        }
    }
    fn for_morris_prev(root: &Rc<RefCell<TreeNode>>) {
        let mut cur_node: Option<Rc<RefCell<TreeNode>>> = Some(Rc::clone(root));
        // 可以找到cur节点对应的左子树中最右边的节点
        while cur_node.is_some() {
            let cur = Rc::clone(cur_node.as_ref().unwrap());
            if let Some(most_right) = cur.borrow().get_child(1) {
                // 这里的“most_right”即当前左子树中位于最右边的节点，即“前驱节点”
                let mut most_right = Rc::clone(most_right);
                while let Some(right_r_c) = Rc::clone(&most_right).borrow().get_child(0) {
                    if Rc::clone(right_r_c) == cur {
                        break;
                    } else {
                        most_right = Rc::clone(right_r_c);
                    }
                }
                // 到这里之后，便相当于找到了前驱节点。
                let most_right = most_right;
                if most_right.borrow().get_child(0).is_none() {
                    // 此时most_right.right == None，故建立线索指针
                    most_right.borrow_mut().l_child = Some(Rc::clone(&cur));
                    println!("{}", cur.borrow()); // 要建立线索指针了，即找到最右边了，也需要打印
                    cur_node = Some(Rc::clone(cur.borrow().get_child(1).as_ref().unwrap()));
                    continue;
                } else {
                    // 此时most_right.right == cur，故删除线索指针
                    most_right.borrow_mut().r_child = None;
                }
            } else {
                println!("{}", cur.borrow()); // 此时已经到了最左边的节点，所以打印
            }

            cur_node = match cur.borrow().get_child(0) {
                Some(r_c) => Some(Rc::clone(r_c)),
                None => None,
            };
        }
    }
    fn for_layerorder(root: &Rc<RefCell<TreeNode>>) {
        let mut queue: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::new();
        queue.push_back(Rc::clone(root));
        while let Some(node) = queue.pop_front() {
            let node = node.borrow();
            if let Some(l_c) = node.get_child(1) {
                queue.push_back(Rc::clone(l_c));
            }
            if let Some(r_c) = node.get_child(0) {
                queue.push_back(Rc::clone(r_c));
            }
            println!("{}", node);
        }
    }
    fn for_postorder(root: &Rc<RefCell<TreeNode>>) {
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
        let mut node: Option<Rc<RefCell<TreeNode>>> = Some(Rc::clone(root));
        let mut prev_node: Option<Rc<RefCell<TreeNode>>> = None;
        while !stack.is_empty() || node.is_some() {
            // 找最左边子节点
            while let Some(cur) = node {
                stack.push(Rc::clone(&cur));
                node = match cur.borrow().get_child(1) {
                    Some(l_c) => Some(Rc::clone(l_c)),
                    None => None,
                };
            }
            // 找到之后弹出来
            node = stack.pop();
            // 查看这个子节点是否能够打印
            let can_print = match &node {
                // 如果存在右子节点则需要判断这个子节点是不是打印过了
                // 可以知道的是，如果右子节点被打印了，那么一定是这个节点的前面那一个
                Some(cur) => match cur.borrow().get_child(0) {
                    Some(l_c) => l_c == prev_node.as_ref().unwrap(),
                    None => true,
                },
                None => false,
            };
            // 如果可以打印就打印
            // 如果不可以打印，就先把右子节点入栈，在下一次循环里判断右子节点是否能够被打印
            if can_print {
                // 还有一点，如果一个节点打印了，就记录一下，以便于下次循环判断这个节点是不是某个节点的右子节点
                println!("{}", node.as_ref().unwrap().borrow());
                prev_node = node;
                // 当前节点需要指向None，负责这个节点会被重新入栈，从而陷入死循环
                node = None;
            } else {
                if let Some(cur) = node {
                    stack.push(Rc::clone(&cur));
                    node = match cur.borrow().get_child(0) {
                        Some(r_c) => Some(Rc::clone(r_c)),
                        None => None,
                    }
                }
            }
        }
    }
    fn for_inorder(root: &Rc<RefCell<TreeNode>>) {
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
        let mut node: Option<Rc<RefCell<TreeNode>>> = Some(Rc::clone(root));
        while !stack.is_empty() || node.is_some() {
            if let Some(cur) = node {
                // 只要这个节点的左子节点有值，那就在入栈后移动到它的左子节点
                stack.push(Rc::clone(&cur));
                node = match cur.borrow().get_child(1) {
                    Some(l_c) => Some(Rc::clone(l_c)),
                    None => None,
                };
            } else {
                // 此时一定是到了某个节点左子节点不存在的时候，开始弹栈
                if let Some(cur) = stack.pop() {
                    let cur = cur.borrow();
                    // 弹出来的节点可以直接输出
                    println!("{}", cur);
                    // 并移动到其右子节点以便于接下来找右子节点的左孩子
                    node = match cur.get_child(0) {
                        Some(r_c) => Some(Rc::clone(r_c)),
                        None => None,
                    };
                }
            }
        }
    }
    fn for_preorder(root: &Rc<RefCell<TreeNode>>) {
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
        stack.push(Rc::clone(root));
        while let Some(node) = stack.pop() {
            // 每次循环都先将树的左子节点和右子节点入栈
            // 注意入栈顺序，栈的特点是先进后出，先序遍历是先打印左子节点后在打印的右子节点
            let node = node.borrow();
            if let Some(l_c) = node.get_child(1) {
                stack.push(Rc::clone(l_c));
            }
            if let Some(r_c) = node.get_child(0) {
                stack.push(Rc::clone(r_c));
            }
            // 左右子节点入完栈后打印当前节点即可，之后的循环就会依次弹出当前节点的左右节点以进行打印了
            println!("{}", node);
        }
    }
}

fn init_tree() -> TreeNode {
    let mut _root: TreeNode = TreeNode::new(1);

    _root.set_child(1, TreeNode::new(2));
    _root.set_child(0, TreeNode::new(3));

    let node1: Rc<RefCell<TreeNode>> = Rc::clone(&_root.get_child(1).as_ref().unwrap());
    let mut node1: RefMut<TreeNode> = node1.borrow_mut();

    node1.set_child(1, TreeNode::new(4));
    node1.set_child(0, TreeNode::new(5));

    let node2: Rc<RefCell<TreeNode>> = Rc::clone(&node1.get_child(0).as_ref().unwrap());
    let mut node2: RefMut<TreeNode> = node2.borrow_mut();

    node2.set_child(1, TreeNode::new(6));
    node2.set_child(0, TreeNode::new(7));

    _root
}
